export function searchInsert(nums: number[], target: number): number {
    return binarySearchInsert(nums, target, 0, nums.length-1);
};

function binarySearchInsert(nums: number[], target: number, start: number, end: number): number {

    if (start >= end) {
        if (nums[start] >= target) return start;
        return start+1;
    }

    const midIdx = ((end - start) >> 1) + start;

    if (nums[midIdx] >= target && nums[midIdx-1]< target) return midIdx;

    if (nums[midIdx] < target && nums[midIdx+1]>=target) return midIdx+1;

    if (nums[midIdx] >= target) { // 用左半区
        return binarySearchInsert(nums, target, start, midIdx);
    }

    // nums[midIdx] < target 的情况
    return binarySearchInsert(nums, target, midIdx+1, end);
}